#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
#define MAXSIZE 100

typedef struct TreeNode{
  ElemType data;
  TreeNode *left;
  TreeNode *right;
}TreeNode,*BiTree;

typedef struct{
  BiTree *data;
  int top;
}Stack;

typedef struct 
{
	TreeNode *data;
	int front;
	int rear;
}Queue;

//初始化
Stack* initStack()
{
	Stack *s = (Stack*)malloc(sizeof(Stack));
	s->data = (BiTree*)malloc(sizeof(BiTree) * MAXSIZE);
	s->top = -1;
	return s;
}

//判断栈是否为空
int isSEmpty(Stack *s)
{
	if (s->top == -1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//进栈/压栈
int push(Stack *s, BiTree e)
{

	if (s->top >= MAXSIZE - 1)
	{
		printf("满了\n");
		return 0;
	}
	s->top++;
	s->data[s->top] = e;
	return 1;
}

//出栈
int pop(Stack *s, BiTree *e)
{
	if (s->top == -1)
	{
		printf("空的\n");
		return 0;
	}
	*e = s->data[s->top];
	s->top--;
	return 1;
}

//获取栈顶元素
int getTop(Stack *s, BiTree *e)
{
	if (s->top == -1)
	{
		printf("空的\n");
		return 0;
	}
	*e = s->data[s->top];
	return 1;
}



char str[] = "ABDH#K###E##CFI###G#J##";
int index = 0;

void createTree(BiTree *t){
  ElemType ch;
  ch=str[index++];
  if(ch=='#'){
    *t=NULL;
  }else{
    *t=(BiTree)malloc(sizeof(TreeNode));
    (*t)->data=ch;
    createTree(&(*t)->left);
    createTree(&(*t)->right);
  }
}

//递归
//前序遍历
void preOrder(BiTree t){
  if(t==NULL)return;
  printf("%c ",t->data);
  preOrder(t->left);
  preOrder(t->right);
}
//中序遍历
void inOrder(BiTree t){
  if(t==NULL)return;
  inOrder(t->left);
  printf("%c ",t->data);
  inOrder(t->right);
}
//后缀遍历
void postOrder(BiTree t){
  if(t==NULL)return;
  postOrder(t->left);
  postOrder(t->right);
  printf("%c ",t->data);
}

//非递归
//前序遍历
void iterPreOrder(Stack *s,BiTree t){
  while(t!=NULL||isSEmpty(s)!=1){
    while(t!=NULL){
      printf("%c ",t->data);
      push(s,t);
      t=t->left;
    }
    pop(s,&t);
    t=t->right;
  }
}
//中序
void iterInOrder(Stack *s,BiTree t){
  while(t!=NULL||isSEmpty(s)==0){
    while(t!=NULL){
      push(s,t);
      t=t->left;
    }
    pop(s,&t);
    printf("%c ",t->data);
    t=t->right;
  }
}
//后序...


int main(){
  BiTree T;
	createTree(&T);
	Stack *s = initStack();
	//iterPreOrder(s, T);
	//printf("\n");
	postOrder(T);
	printf("\n");
	iterInOrder(s, T);
	return 0;
}